package one;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的中序遍历
 * 时间复杂度：O(n)
 * 思路：深度优先，递归
 */
public class InorderTraversal {
    private List<Integer> ans = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        find(root);
        return ans;
    }
    private void find(TreeNode root){
        if(root == null) return;
        find(root.left);
        ans.add(root.val);
        find(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2), null);
        List<Integer> ans = new InorderTraversal().inorderTraversal(root);
        for(int d : ans){
            System.out.print(d + " ==> ");
        }
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(){}
    public TreeNode(int val){
        this.val = val;
    }
    public TreeNode(int val, TreeNode left, TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
